package com.husk.leetcode.dp;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = bf.readLine().split(" ");
        int money = Integer.parseInt(strs[0]);
        int n = Integer.parseInt(strs[1]);

        Good[] goods = new Good[n + 1];
        for (int i = 1; i <= n; i++) {
            strs = bf.readLine().split(" ");
            int v = Integer.parseInt(strs[0]);
            int p = Integer.parseInt(strs[1]);
            int q = Integer.parseInt(strs[2]);
            goods[i] = new Good(v, p, q);

            if (q > 0) {
                if (goods[q].a1 == 0) {
                    goods[q].setA1(i);
                } else {
                    goods[q].setA2(i);
                }
            }
        }

        int[][] dp = new int[n + 1][money + 1];
        for (int i = 1; i <= n; i++) {
            int v = 0, v1 = 0, v2 = 0, v3 = 0, tempdp = 0, tempdp1 = 0, tempdp2 = 0, tempdp3 = 0;

            v = goods[i].v;

            tempdp = goods[i].p * v; //只有主件

            if (goods[i].a1 != 0) {//主件加附件1
                v1 = goods[goods[i].a1].v + v;
                tempdp1 = tempdp + goods[goods[i].a1].v * goods[goods[i].a1].p;
            }

            if (goods[i].a2 != 0) {//主件加附件2
                v2 = goods[goods[i].a2].v + v;
                tempdp2 = tempdp + goods[goods[i].a2].v * goods[goods[i].a2].p;
            }

            if (goods[i].a1 != 0 && goods[i].a2 != 0) {//主件加附件1和附件2
                v3 = goods[goods[i].a1].v + goods[goods[i].a2].v + v;
                tempdp3 = tempdp + goods[goods[i].a1].v * goods[goods[i].a1].p + goods[goods[i].a2].v * goods[goods[i].a2].p;
            }

            for (int j = 1; j <= money; j++) {
                if (goods[i].q > 0) {   //当物品i是附件时,相当于跳过
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                    if (j >= v && v != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v] + tempdp);
                    }
                    if (j >= v1 && v1 != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v1] + tempdp1);
                    }
                    if (j >= v2 && v2 != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v2] + tempdp2);
                    }
                    if (j >= v3 && v3 != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v3] + tempdp3);
                    }
                }
            }
        }
        System.out.println(dp[n][money]);
    }


    /**
     * 定义物品类
     */
    private static class Good {
        public int v;  //物品的价格
        public int p;  //物品的重要度
        public int q;  //物品的主附件ID

        public int a1 = 0;   //附件1ID
        public int a2 = 0;   //附件2ID

        public Good(int v, int p, int q) {
            this.v = v;
            this.p = p;
            this.q = q;
        }

        public void setA1(int a1) {
            this.a1 = a1;
        }

        public void setA2(int a2) {
            this.a2 = a2;
        }
    }
}